﻿using UnityEngine;
using System.Collections;

public class AStar : MonoBehaviour {
	//variables used by the algorithm
	public GridCell[] openList = new GridCell[1000];
	public GridCell[] closedList = new GridCell[1000];
	public int openListLength;
	public int closedListLength;

	public bool allowDiagonalMovement;
	public bool useBestFirstSearch;

	void Start(){
		openList = new GridCell[250];
		closedList = new GridCell[250];
	}

	//the A* Algorithm
	public GridCell[] calculatePath(){
		float startTime = Time.realtimeSinceStartup;
		clearLists();
		GridCell currentGridCell = GameController.player.currentGridCell;
		GridCell targetGridCell = GameController.player.destinationGridCell;
		Vector2 playerCurrentGridCellBoardPosition = GameController.player.currentGridCellBoardPosition;
		if(!targetGridCell.walkable && !GridCell.areEqual(currentGridCell, targetGridCell)){
			Debug.Log ("clicked on non walkable terrain.");
			//return null;
			int xValue;
			int yValue;
			xValue = ((targetGridCell.boardPosition.x==0) ? 1 : -1);
			yValue = ((targetGridCell.boardPosition.y==GameController.gc.boardHeight-1) ? -1 : 1);
			targetGridCell = GameController.gc.board[(int) targetGridCell.boardPosition.x+xValue,(int) targetGridCell.boardPosition.y+yValue];
		}
		while(!GridCell.areEqual(currentGridCell, targetGridCell)){
			//generate children nodes.
			if(closedListLength > 1000){
				Debug.Log ("inifinite looped");
				return null;
			}
			for(int i = -1; i <= 1; i++){
				for(int j = -1; j <= 1; j++){
					if((allowDiagonalMovement && (i!=0 || j!=0)) || (!allowDiagonalMovement && (i==0 || j==0 )&& !(i==0 && j==0))){
						Vector2 thisPosition = new Vector2(0f,0f);
						thisPosition = currentGridCell.boardPosition;
						//if this is a valid board position
						int xPosition = (int) thisPosition.x + i;
						int yPosition = (int) thisPosition.y + j;
						if(xPosition >= 0 && xPosition < GameController.gc.boardWidth  && yPosition >= 0 && yPosition < GameController.gc.boardHeight){
							if(GameController.gc.board[xPosition,yPosition].walkable){
								//has this node already been added to the closed list?
								if(!isInClosedList(GameController.gc.board[xPosition,yPosition])){
									//assign g, h, and f values for the possibleNode.

									//diagonal movement requires g values of 14
									int gValue = 0;
									if(i!=0 && j!=0){
										gValue = GameController.gc.board[(int) thisPosition.x,(int) thisPosition.y].gValue + 14;
									}
									else{
										gValue = GameController.gc.board[(int) thisPosition.x,(int) thisPosition.y].gValue + 10;
									}
									if(useBestFirstSearch){
										gValue = 0;
									}
									int hValue = calculateHValue(GameController.gc.board[xPosition,yPosition], GameController.gc.board[(int) targetGridCell.boardPosition.x,(int) targetGridCell.boardPosition.y]);
									int fValue = gValue + hValue;
									//update the nodes f, g and h values if a new lower one has been calculated.
									if(GameController.gc.board[xPosition,yPosition].fValue > fValue){
										GameController.gc.board[xPosition,yPosition].gValue = gValue;
										GameController.gc.board[xPosition,yPosition].hValue = hValue;
										GameController.gc.board[xPosition,yPosition].fValue = fValue;
										GameController.gc.board[xPosition,yPosition].parentGridCell = GameController.gc.board[(int) thisPosition.x, (int) thisPosition.y];
									}
									//add the child to the open list
									if(!isInOpenList(GameController.gc.board[xPosition,yPosition])){
										openList[openListLength] = GameController.gc.board[xPosition,yPosition];
										//Debug.Log (xPosition + ", " + yPosition + " added to open list");
										openListLength++;
									}
								}
							}
						}
					}
				}
			}
			//add the current node to the closed list.

			//is the current node is already in the closed list, then no path can be found.
			if(isInClosedList(GameController.gc.board[(int) currentGridCell.boardPosition.x, (int) currentGridCell.boardPosition.y])){
				Debug.Log ("no path could be found, closed list full");
				return null;
			}
			closedList[closedListLength] = GameController.gc.board[(int) currentGridCell.boardPosition.x, (int) currentGridCell.boardPosition.y];
			closedListLength++;
			//make the currentNode be the node in the open list with the smallest f value.
			Vector2 currentGridCellBoardPosition = getGridCellWithLowestFValue();
			//if the open list is empty, return null.
			if(currentGridCellBoardPosition.x==-999f && currentGridCellBoardPosition.y==-999f){
				Debug.Log ("no path could be found, open list empty");
				return null;
			}
			currentGridCell = GameController.gc.board[(int) currentGridCellBoardPosition.x, (int) currentGridCellBoardPosition.y];
			removeFromOpenList(currentGridCellBoardPosition);

		}
		GridCell[] path = new GridCell[1000];
		GridCell[] correctPath = new GridCell[1000];
		int index = 0;
		while(currentGridCell.parentGridCell!=null && index<1000 /*&& (currentGridCell.parentGridCell.boardPosition.x != playerCurrentGridCellBoardPosition.x || currentGridCell.parentGridCell.boardPosition.y != playerCurrentGridCellBoardPosition.y)*/){
			path[index] = GameController.gc.board[(int) currentGridCell.boardPosition.x, (int) currentGridCell.boardPosition.y];
			index++;
			currentGridCell = GameController.gc.board[(int) currentGridCell.boardPosition.x, (int) currentGridCell.boardPosition.y].parentGridCell;
		}
		int jindex = 0;
		while(index >0){
			correctPath[jindex] = path[index-1];
			jindex++;
			index--;
		}
		float endTime = Time.realtimeSinceStartup;
		if(GameController.gc.showStatInfo){
			Debug.Log("Total Nodes Expanded: " + openListLength);
			Debug.Log ("Total Nodes Expanded On: " + closedListLength);
			Debug.Log ("Total Time for calculating path: "+ (endTime - startTime));
		}
		return correctPath;
	}

	//Calculate the Heuristice Value for a node.
	int calculateHValue(GridCell possibleNode, GridCell targetGridCell){
		int hValue = 0;
		int xDifference = Mathf.Abs((int) (GameController.gc.board[(int) possibleNode.boardPosition.x, (int) possibleNode.boardPosition.y].boardPosition.x - GameController.gc.board[(int) targetGridCell.boardPosition.x, (int) targetGridCell.boardPosition.y].boardPosition.x));
		int yDifference = Mathf.Abs((int) (GameController.gc.board[(int) possibleNode.boardPosition.x, (int) possibleNode.boardPosition.y].boardPosition.y - GameController.gc.board[(int) targetGridCell.boardPosition.x, (int) targetGridCell.boardPosition.y].boardPosition.y));
		int minValue = Mathf.Min(xDifference, yDifference);
		int difference = Mathf.Abs(xDifference - yDifference);
		if(allowDiagonalMovement){
			hValue = minValue * 14 + difference * 10;
		}
		else{
			hValue = (xDifference + yDifference) * 10;
		}
		return hValue;
	}

	//is the current potential node in the closed list?
	bool isInClosedList(GridCell possibleNode){
		for(int i = 0; i < closedListLength; i++){
			if(closedList[i] != null){
				if(GridCell.areEqual(possibleNode,closedList[i])){
					return true;
				}
			}
		}
		return false;
	}
	// is the current possible node already in the open list?
	bool isInOpenList(GridCell possibleNode){
		for(int i = 0; i < openListLength; i++){
			if(openList[i]!=null){
				if(GridCell.areEqual(possibleNode,openList[i])){
					return true;
				}
			}
		}
		return false;
	}

	//get the grid cell with the lowest f value.
	Vector2 getGridCellWithLowestFValue(){
		GridCell gridCell = openList[0];
		int min;
		min = ((gridCell == null) ? 999 : gridCell.fValue);
		int indexOf = 0;
		for(int i = 1; i < openListLength; i++){
			if(openList[i]!=null){
				if(GameController.gc.board[(int) openList[i].boardPosition.x,(int) openList[i].boardPosition.y].fValue < min){
					gridCell = openList[i];
					min = GameController.gc.board[(int) openList[i].boardPosition.x,(int) openList[i].boardPosition.y].fValue;
					indexOf = i;
				}
			}
		}
		if(indexOf==0 && gridCell==null){
			return new Vector2(-999,-999);
		}
		openList[indexOf].fValue = 999;
		return gridCell.boardPosition;
	}

	void removeFromOpenList(Vector2 boardPosition){
		for(int i = 0; i < openListLength; i++){
			if(openList[i]!=null){
				if(openList[i].boardPosition.x==boardPosition.x && openList[i].boardPosition.y==boardPosition.y){
					openList[i] = null;
				}
			}
		}
	}

	void clearLists(){
		for(int i = 0; i < 250; i++){
			openList[i] = null;
			closedList[i] = null;
			openListLength = 0;
			closedListLength = 0;
		}
	}
}
